package com.practice.dp;

import java.util.Arrays;

public class StackedBox {
	private int W = 5;
	private int H = 6;
	private int D = 7;
	
	private int[][][] dp;
	
	public int solve(int w, int h, int d) {
		dp = new int[w+1][h+1][d+1];
		for (int i=0; i<=w; i++)
			for (int j=0; j<=h; j++)
				for (int k=0; k<=d; k++)
					dp[i][j][k] = -1;
		dp[W][H][D] = 1;
		return stack(w, h, d);
	}
	
	private int stack(int w, int h, int d) {
		int[] m = new int[]{w, h, d};
		Arrays.sort(m);
		if (m[0] < W) return 0;
		if (dp[m[0]][m[1]][m[2]] >= 0) return dp[m[0]][m[1]][m[2]];
		
		int max = 0;
		max = Math.max(max, directional(m[0], m[1], m[2]));
		max = Math.max(max, directional(m[0], m[2], m[1]));
		
		max = Math.max(max, directional(m[1], m[0], m[2]));
		max = Math.max(max, directional(m[1], m[2], m[0]));
		
		max = Math.max(max, directional(m[2], m[0], m[1]));
		max = Math.max(max, directional(m[2], m[1], m[0]));
		
		dp[m[0]][m[1]][m[2]] = max;
		return max;
	}
	
	private int directional(int w, int h, int d) {
		if (w<W || h<H || d<D) return 0;
		int max = 1 + stack(w-W, h, d);
		max += Math.max(stack(W, h-H, D) + stack(W, h, d-D), stack(W, H, d-D) + stack(W, h-H, d));
		return max;
	}
}
